I. Field of the Invention
The invention generally relates to serial Viterbi decoders and in particular to serial Viterbi decoders for use within Code Division Multiple Access (CDMA) wireless communication systems.
II. Description of the Related Art
FIG. 1 is an illustrative block diagram of a variable rate CDMA transmission system 10 described in the Telecommunications Industry Association's Interim Standard TIA/EIA/IS-95-A Mobile Station-Base Station Compatibility Standard for Dual-Mode Wideband Spread Spectrum Cellular System. This transmission system may be provided, for example, within a base station of a cellular transmission system for use in transmitting signals to mobile telephones within a cell surrounding the base station.
An input line 11 provides a speech or data signal which may be analog or digital. In the following example, it will be assumed that the input signal is a speech signal. The input line may be an analog or digital public switched telephone network (PSTN) line or other speech signal source. If the input speech signal is analog, the signal is sampled and digitized by an analog to digital converter (not shown). A variable rate data source 12 receives the digitized samples of the speech signal and encodes the signal to provide packets of encoded speech of equal frame lengths. Variable rate data source 12 may, for example, convert the digitized samples of the input speech to digitized speech parameters representative of the input voice signal using Linear Predictive Coding (LPC) techniques. In one embodiment, the variable rate data source is a variable rate vocoder as described in detail in U.S. Pat. No. 5,414,796. Variable rate data source 12 provides variable rate packets of data at four possible frame rates 9600 bps, 4800 bps, 2400 bps and 1200 bps, referred to herein as full, half, quarter, and eighth rates. Packets encoded at full rate contain 172 information bits, samples encoded at half rate contain 80 information bits, samples encoded at quarter rate contain 40 information bits and samples encoded at eighth rate contain 16 information bits. The packets regardless of size all are one frame length in duration, i.e. 20 ms. Other systems may employ other data rates or packet sizes. Herein, the terms "frame" and "packet" may be used interchangeably.
The packets are encoded and transmitted at different rates to compress the data contained therein based, in part, on the complexity or amount of information represented by the frame. For example, if the input voice signal includes little or no variation, perhaps because the speaker is not speaking, the information bits of the corresponding packet may be compressed and encoded at eighth rate. This compression results in a loss of resolution of the corresponding portion of the voice signal but, given that the corresponding portion of the voice signal contains little or no information, the reduction in signal resolution is not typically noticeable. Alternatively, if the corresponding input voice signal of the packet includes much information, perhaps because the speaker is actively vocalizing, the packet is encoded at full rate and the information bits of the packet are not compressed at all.
This compression and encoding technique is employed to limit, on the average, the amount of signals being transmitted at any one time to thereby allow the overall bandwidth of the transmission system to be utilized more effectively to allow, for example, a greater number of telephone calls to be processed at any one time.
The variable rate packets generated by data source 12 are provided to packetizer 13 which selectively appends cyclic redundancy check (CRC) bits and tail bits. The variable rate packets from packetizer 13 are then provided to encoder 14 which encodes the bits of the variable rate packets for error detection and correction purposes. In one embodiment, encoder 14 is a rate 1/3 convolutional serial Viterbi encoder. The convolutionally encoded symbols are then provided to a modulator 16 which generates a modulated signal. An implementation of a CDMA modulator is described in detail in U.S. Pat. Nos. 5,103,459 and 4,901,307. The modulated signal is then provided to digital to analog converter 22 for conversion to an analog signal, then provided to transmitter 24 which upconverts and amplifies the signal for transmission through antenna 26.
FIG. 2 illustrates pertinent components of a mobile telephone 28 or other mobile station receiving the transmitted signal. The signal is received by antenna 30, downconverted and amplified, if necessary, by receiver 31 and demodulated by a demodulator 32 into a stream of symbols which remain convolutionally encoded. The signal is then provided to a serial Viterbi decoder 34 which decodes a convolutionally encoded stream of symbols. The decoder also subdivides the received signal into packets and determines the corresponding frame rate for each packet. The frame rate may be determined, for example, by detecting the duration of individual bits of the frame. Aspects of an exemplary serial Viterbi decoder are described in now abandoned U.S. patent application Ser. No. 08/126,477 filed Sep. 24, 1993, assigned to the assignee of the present invention and incorporated by reference herein.
To decode the stream of symbols, decoder 34 employs a branch error metric block 36 which receives symbols from the demodulator and an Add Compare Select block (ACS) 38 which produces decision bits based upon the symbols. To enhance performance, the decoder chains back from what it considers the best state metric using a chainback block 40 which processes the decision bits received from ACS 38. In each process cycle, 2.sup.K-1 decision bits are stored by the chainback block in a chainback RAM 41 wherein K is the constraint length of the code employed by the encoder. The state with the lowest best state metric is passed from the ACS to the chainback block as the best state.
Once L process cycles have elapsed, chaining back begins. The chainback operation is controlled by a chainback controller 42. The process of chaining back is performed by reading from the chainback RAM the decision bit for the best state for the previous process cycle (L-1). The read decision bit is shifted into the least significant bit of best state. The chainback block next reads from the chainback RAM the decision bit corresponding to the new value of best state for process cycle L-2. This process is performed a total of L times ultimately reading the decision bit of the calculated best state for process cycle 0. The final decision bit is the decoded information bit. Each bit that is read modifies the address of the subsequent read. In the next process cycle, L+1, the whole procedure is repeated again, reading state decision bits from process cycles L down to 1. This continues for as many process cycles as necessary to retrieve the required number of information bits for the particular system.
Specific examples of chainback operations are illustrated in FIG. 3. If the first chainback occurs after 4 process cycles and the best state is 101 after four process cycles, then the reads performed to complete the chainback process are those shown by entries shaded in gray. First state 101 of process cycle 3 will be read, then state 011 of process cycle 2, then state 111 of process cycle 1, then state 110 of process cycle 0, resulting in an output decision bit of 0. At the beginning of process cycle 5, if the best state is 010,then the first read results in the best state being set to 101. Hence, the next three reads will follow the same path as before, namely the path of entries shaded in gray. This time though the output decision bit is read from the process cycle 1 entry thereby resulting in a decision bit of 0. At the beginning of process cycle 6, if the best state is 001, then the first read results in the best state being set to 010. Hence, the next three reads will again follow the same path as before. This time the output decision bit is read from the process cycle 2 entry thereby resulting in a decision bit of 1.
Referring back to FIG. 2, ultimately, decoder 34 provides a decoded packet along with a signal identifying a detected frame rate for the packet. Both are forwarded to a frame quality check unit 43 which attempts to verify that no transmission errors or frame rate detection errors occurred. In the exemplary embodiment, frame quality check unit 43 performs a CRC, a symbol error rate check and a Yamamoto metric check. To perform the symbol error rate check, frame quality check unit 43 re-encodes symbols found in the decoded packet and compares the re-encoded symbols with symbols input to the frame quality check unit to detect any differences. To perform the Yamamoto metric check, frame quality check unit 43 applies the received frames to a trellis path decoder and determines whether a resulting metric is acceptable. Acceptable frames are routed to a speech decoder 44 for conversion back to digitized voice signals. The digitized voice signals are converted to analog signals by a digital to analog converter (not shown) for ultimate output through a speaker 46 of the mobile telephone such that an operator of the telephone can hear the speech signal that had been originally input to the overall system along line 11 of FIG. 1.
Although not shown, the mobile telephone of FIG. 2 may have additional components for inputting an analog speech signal from the operator of the mobile telephone and for processing and transmitting the signal using CDMA techniques. The additional components of the mobile telephone may be similar to the components shown in FIG. 1. Moreover, although not shown, the transmission system of FIG. 1 may have additional components provided for receiving the transmitted signal from the mobile telephone and for processing and outputting the signal as an analog or digital speech signal, perhaps onto a PSTN line. The additional components of the system of FIG. 1 may be similar to the components shown in FIG. 2.
Thus an important component of the overall system is the serial Viterbi decoder provided for decoding the transmitted symbols. As noted, decoder 34 exploits a chainback operation to enhance performance. To gain a significant enhancement in performance the length of the chainback is preferably at least 3 to 5 times the constraint length of the encoder (K=9 for CDMA) with better performance with larger chainback depth. However, the larger the length of the chainback, the greater amount of circuit area and power required to implement the chainback. Larger circuit area is required because a larger memory is required to store the decision bits of the chainback. For example, for a constraint K encoder, 2.sup.K-1 decision bits are stored for each information bit. With a chainback depth of L, L*2.sup.K-1 bits need to be stored. Greater power is required because, in order to generate one bit of data, the chainback block needs to perform L reads. Also, a greater delay occurs before the chainback operation is completed. Although described with respect to a CDMA system employing a serial Viterbi decoder, similar problems can occur in most systems employing serial Viterbi decoders and in related decoder systems as well.
Accordingly, it would be desirable to provide a technique for substantially reducing the power usage and processing time of the chainback block while only requiring a small increase in area and it is to that end that aspects of the present invention are primarily drawn.